package Boogle_and_Word_Ladder;

import java.io.BufferedReader;
import java.io.FileReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

public class word_ladder_II {
	
	public word_ladder_II(){
		
	}

	private static final NavigableSet<String> dictionary;
	static{
		dictionary = new TreeSet<String>();
		try{
			BufferedReader br = new BufferedReader(new FileReader("src/Boogle_and_Word_Ladder/1.txt"));
			String line;
			while((line=br.readLine())!=null){
				dictionary.add(line.split(":")[0]);
			}
		}
		catch(Exception e){
			throw new RuntimeException(e);
		}
	}
	
	public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict){
		HashMap<String, HashSet<String>> visited = new HashMap<String, HashSet<String>>();
		HashMap<String, Integer> level = new HashMap<String, Integer>();
		Queue<String> queue = new LinkedList<String>();
		ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
		
		//Edge cases
		if(start==null || end==null || start.length()!=end.length())
			return ret;
		//store the path from start, initiate start case
		HashSet<String> path = new HashSet<String>();
		visited.put(start, path);
		level.put(start, 1);
		queue.add(start);
		//minimum length
		int min_len = Integer.MAX_VALUE;
		
		while(!queue.isEmpty()){
			String s = queue.remove();
			char[] ch = s.toCharArray();
			for(int i=0;i<s.length();++i){
				char ch_4_backtrack = ch[i];
				for(int j=0;j<26;++j){
					ch[i] = (char)('a'+j);
					String s2 = String.valueOf(ch);
					//avoid circle, check whether it's in the dictionary or have better choice
					if(dict.contains(s2) && (!level.containsKey(s2) || (level.containsKey(s2) && level.get(s2)>level.get(s)))){
						//update the ancestor
						if(visited.containsKey(s2))
							visited.get(s2).add(s);
						//new node
						else{
							path = new HashSet<String>();
							path.add(s);
							visited.put(s2, path);
							level.put(s2, level.get(s)+1);
							queue.add(s2);
						}
					}
					
					if(s2.equals(end)){
						//found the path that have minimum length
						if(level.get(s)<min_len){
							ArrayList<String> entry = new ArrayList<String>();
							entry.add(end);
							ret.addAll(backtrace(s, visited, entry));
							min_len = level.get(s)+1;
						}
						//if level.get(s)>=min_len, then here are better choice
						else{
							break;
						}
					}
				}
				//backtrack to handle all the cases
				ch[i] = ch_4_backtrack;
			}
		}
		
		return ret;
	}
	
	
	private ArrayList<ArrayList<String>> backtrace(String end, HashMap<String, HashSet<String>> visited, ArrayList<String> path){
		ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
		ArrayList<String> entry = new ArrayList<String>(path);
		entry.add(end);
		if(visited.get(end).size()==0){
			ret.add(entry);
			return ret;
		}
		for(String s:visited.get(end)){
			ret.addAll(backtrace(s, visited, entry));
		}
		return ret;
	}
	

    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> ret = new ArrayList<String>();
        if(s.isEmpty()) return ret;
        int len = s.length();
        boolean[] in = new boolean[len+1];
        in[0] = true;
        for(int i=0;i<len+1;++i){
            for(int j=0;j<i;++j){
                if(in[j] && dict.contains(s.substring(j,i))){
                    in[i] = true;
                    continue;
                }
            }
        }
        
        if(in[len]==true){
            HashMap<Integer,ArrayList<String>> map = new HashMap<Integer,ArrayList<String>>();
            for(int i=0;i<len+1;++i)
                map.put(i, new ArrayList<String>());
            map.get(0).add("");
            for(int i=0;i<len+1;++i){
                for(int j=0;j<i;++j){
                    if(in[i]){
                        ArrayList<String> prelist = map.get(i);
                        ArrayList<String> newlist = new ArrayList<String>(map.get(j));
                        for(String str: prelist){
                            if(!str.isEmpty())
                                str+=" ";
                            newlist.add(s);
                        }
                        map.put(j,newlist);
                    }
                }
            }
            ret = map.get(len);
        }
        return ret;
        
    }
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Iterator<String> iterator = dictionary.iterator();
		HashSet<String> dict = new HashSet<>();
		while(iterator.hasNext()){
			dict.add(iterator.next());
		}
		
		word_ladder_II test = new word_ladder_II();
		ArrayList<ArrayList<String>> list = test.findLadders("hit", "cog", dict);
		for(int i=0;i<list.size();++i){
			for(int j=0;j<list.get(i).size();++j){
				System.out.print(list.get(i).get(j)+" ");
			}
			System.out.println();
		}
		

	}
}